Hahs表存儲結構

字符串Hash

1.1拉鏈法

案例代碼如下:

#include<iostream>
#include<cstring>
using namespace std;
?
const int N = 100003;
int h[N],e[N],ne[N],idx;
?
//插入操作
void insert(int x)
{
? ? int k = (x%N + N) % N;
? ? e[idx] = x;
? ? ne[idx] = h[k];
? ? h[k] = idx++;
? ??
}
?
//查詢操作
bool find(int x)
{
? ? int k = (x%N+N) %N;
? ? for(int i = h[k];i != -1;i = ne[i])
? ? {
? ? ? ? if(e[i] == x)
? ? ? ? {
? ? ? ? ? ? return true;
? ? ? ? }
? ? }
? ? return false;
}
?
int main()
{
? ?int n;
? ?scanf("%d",&n);
? ?
? ?//清空槽
? ?memset(h,-1,sizeof h);
? ?
? ?while(n --)
? ?{
? ? ? ?char op[2];
? ? ? ?scanf("%s%d",op,&x);
? ? ? ?
? ? ? ?if(*op == 'I') insert(x);
? ? ? ?else
? ? ? ?{
? ? ? ? ? ?if(find(x)) puts("yes")
? ? ? ? ? ? else
? ? ? ? ? ?{
? ? ? ? ? ? ? ?puts("No");
? ? ? ? ? ?}
? ? ? ?}
? ?}
? ?return 0;
}

?